#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct QueueNode
{
    struct QueueNode* next;
    int val;
}QNode;

typedef struct Queue
{
    QNode* qhead;
    QNode* qtail;
}Queue;


typedef struct {
    Queue* QStackA;
    Queue* QStackB;
} MyStack;

QNode* BuyQNode(int x);
Queue* InitQueue();
bool IsQueueEmpty(Queue* que);
void DestoryQUeue(Queue* que);
void QUeuePop(Queue* q);

QNode* BuyQNode(int x)
{
    QNode* tmp = (QNode*)malloc(sizeof(QNode));
    tmp->next = NULL;
    tmp->val = x;
    return tmp;
}

Queue* InitQueue()
{
    Queue* que = (Queue*)malloc(sizeof(Queue));
    que->qhead = que->qtail = NULL;
    return que;
}

bool IsQueueEmpty(Queue* que)
{
    // assert(que);
    return que->qhead == NULL;
}

void DestoryQUeue(Queue* que)
{
    QNode* head = que->qhead;
    while (!IsQueueEmpty(que))
    {
        QUeuePop(que);
    }

}

MyStack* myStackCreate() {
    MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));

    tmp->QStackA = InitQueue();
    tmp->QStackB = InitQueue();
    return tmp;
}

void QUeuePush(Queue* q, int x)
{
    QNode* newnode = BuyQNode(x);
    if (IsQueueEmpty(q))
    {
        q->qhead = q->qtail = newnode;
    }
    else
    {
        q->qtail->next = newnode;
        q->qtail = newnode;
    }
}

void QUeuePop(Queue* q)
{
    if (IsQueueEmpty(q))
        return;
    if (q->qhead == q->qtail)
    {
        free(q->qhead);
        q->qhead = q->qtail = NULL;
    }
    else
    {
        QNode* _next = q->qhead->next;
        free(q->qhead);
        q->qhead = _next;
    }
}

void myStackPush(MyStack* obj, int x) {
    Queue* pushQue = obj->QStackA;
    if (IsQueueEmpty(obj->QStackA))
        pushQue = obj->QStackB;
    QUeuePush(pushQue, x);
}

int myStackPop(MyStack* obj) {
    Queue* popQue = obj->QStackA;
    Queue* pushQue = obj->QStackB;
    if (IsQueueEmpty(popQue))
    {
        popQue = obj->QStackB;
        pushQue = obj->QStackA;
    }

    while (popQue->qhead->next)
    {
        QUeuePush(pushQue, popQue->qhead->val);
        QUeuePop(popQue);
    }
    int ret = popQue->qhead->val;
    QUeuePop(popQue);
    return ret;
}

int myStackTop(MyStack* obj) {
    Queue* que = obj->QStackA;
    if (IsQueueEmpty(obj->QStackA))
        que = obj->QStackB;
    return que->qtail->val;
}

bool myStackEmpty(MyStack* obj) {
    return IsQueueEmpty(obj->QStackA) && IsQueueEmpty(obj->QStackB);
}

void myStackFree(MyStack* obj) {
    DestoryQUeue(obj->QStackA);
    DestoryQUeue(obj->QStackB);
    free(obj->QStackA);
    free(obj->QStackB);
    obj->QStackA = obj->QStackB = NULL;
    free(obj);

}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

int main()
{
    MyStack* stack = myStackCreate();

    myStackPush(stack, 10);
    myStackPush(stack, 11);
    myStackPush(stack, 12);
    
    myStackPop(stack);
    myStackFree(stack);

    return 0;
}